public class Solution {
    static class ListNode{
        private int val;
        private Solution.ListNode next;

        public ListNode(Solution.ListNode next) {
            this.next = next;
        }

        public ListNode(int val, Solution.ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
    public ListNode middleNode(ListNode head){
        if(head == null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
//这里不能是||，因为||无法到达链表的尾部
//两个条件的顺序不能互换，因为fast为空，fast.next就会空指针异常
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    public static void main(String[] args) {
        ListNode node5 = new ListNode(5,null);
        ListNode node4 = new ListNode(4,node5);
        ListNode node3 = new ListNode(3,node4);
        ListNode node2 = new ListNode(2,node3);
        ListNode node1 = new ListNode(1,node2);

        Solution solution = new Solution();
        ListNode middleNode = solution.middleNode(node1);
        System.out.println(middleNode.val);
    }
}
